Basic calculator III

Time: O(N); Space: O(N); hard

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647].

Example 1:

Input: s = “1 + 1”

Output: 2

Example 2:

Input: s = ” 6-4 / 2 “

Output: 4

Example 3:

Input: s = “2 * (5 + 5 * 2) / 3 + (6 / 2 + 8)”

Output: 21

Example 4:

Input: s = “(2 + 6 * 3 + 5 - (3 * 14 / 7 + 2) * 5) + 3”

Output: -12

Note:

  • Do not use the eval built-in library function.

[3]:

class Solution1(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        operands, operators = [], []
        operand = ""
        for i in reversed(range(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0 or not s[i-1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == ')' or s[i] == '*' or s[i] == '/':
                operators.append(s[i])
            elif s[i] == '+' or s[i] == '-':
                while operators and \
                      (operators[-1] == '*' or operators[-1] == '/'):
                    self.compute(operands, operators)
                operators.append(s[i])
            elif s[i] == '(':
                while operators[-1] != ')':
                    self.compute(operands, operators)
                operators.pop()

        while operators:
            self.compute(operands, operators)

        return operands[-1]

    def compute(self, operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)
        elif op == '*':
            operands.append(left * right)
        elif op == '/':
            operands.append(left / right)


[5]:

sol = Solution1()
s = "1 + 1"
assert sol.calculate(s) == 2
s = " 6-4 / 2 "
assert sol.calculate(s) == 4
s = "2*(5+5*2)/3+(6/2+8)"
assert sol.calculate(s) == 21
s = "(2+6* 3+5- (3*14/7+2)*5)+3"
assert sol.calculate(s) == -12